// https://leetcode.cn/problems/shortest-path-to-get-all-keys/
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution
{
private:
    int dist[31][31][64];

    struct Node
    {
        int x, y, s;
    };

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

public:
    int shortestPathAllKeys(vector<string> &grid)
    {
        // 1. 找出@的起点位置和的钥匙总数
        int m = grid.size(), n = grid[0].size();
        memset(dist, 0x3f, sizeof dist); // 很重要，距离先设置成最大的
        int keyNum = 0;
        queue<Node> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '@')
                {
                    q.push({i, j, 0});
                    dist[i][j][0] = 0;
                }
                if (grid[i][j] >= 'a' && grid[i][j] <= 'z')
                    keyNum++;
            }
        }

        // 2.开始找出最有路径
        while (!q.empty())
        {
            Node t = q.front();
            q.pop();
            int distance = dist[t.x][t.y][t.s]; // 距离
            for (int i = 0; i < 4; i++)
            {
                int x = t.x + dx[i], y = t.y + dy[i], s = t.s;
                if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#')
                    continue;
                char c = grid[x][y];

                if (c >= 'a' && c <= 'z')
                {
                    s |= 1 << (c - 'a');
                    if (dist[x][y][s] > distance + 1)
                    {
                        dist[x][y][s] = distance + 1;
                        if (s == (1 << keyNum) - 1)
                            return distance + 1;
                        q.push({x, y, s});
                    }
                }
                else if (c >= 'A' && c <= 'Z')
                {
                    if (s & (1 << (c - 'A')))
                    {
                        // 能开锁
                        if (dist[x][y][s] > distance + 1)
                        {
                            dist[x][y][s] = distance + 1;
                            q.push({x, y, s}); // 将最新的最有的结果加入到队列中去
                        }
                    }
                }
                else
                {
                    if (dist[x][y][s] > distance + 1)
                    {
                        dist[x][y][s] = distance + 1;
                        q.push({x, y, s}); // 将最新的最有的结果加入到队列中去
                    }
                }
            }
        }

        // 最终没有找到合适
        return -1;
    }
};

int main()
{
    Solution so;
    return 0;
}